import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class proJect {
    List<Integer> list=new LinkedList<>();
    Map<Integer,TreeNode> map=new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        dfs1(root);
        dfs2(target,null,0,k);
        return list;
    }
    public void dfs1(TreeNode root){
        if(root.left!=null){
            map.put(root.left.val,root);
            dfs1(root.left);
        }
        if(root.right!=null){
            map.put(root.right.val,root);
            dfs1(root.right);
        }
    }
    public void dfs2(TreeNode node,TreeNode root,int sum,int k){
        if(node==null){
            return;
        }
        if(sum==k){
            list.add(node.val);
            return;
        }
        if(node.left!=root){
            dfs2(node.left,node,sum+1,k);
        }
        if(node.right!=root){
            dfs2(node.right,node,sum+1,k);
        }
        if(map.get(node.val)!=root){
            dfs2(map.get(node.val),node,sum+1,k);
        }
    }



















    public List<Integer> findLonely(int[] nums) {
        List<Integer> list=new LinkedList<>();
        Arrays.sort(nums);
        list.add(nums[0]);
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]==nums[i]||nums[i]==nums[i-1]+1){
                if(!list.isEmpty()&&(nums[i]==list.get(list.size()-1)||nums[i]==list.get(list.size()-1)+1)){
                    list.remove(list.size()-1);
                }
            }else{
                list.add(nums[i]);
            }
        }
        return list;
    }
















    public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
        int sum=0;
        for(int num : nums){
            if(num%2==0){
                sum+=num;
            }
        }
        int[] arr=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            int val=queries[i][0];
            int index=queries[i][1];
            if(nums[index]%2==0){
                sum-=nums[index];
            }
            nums[index]+=val;
            if(nums[index]%2==0){
                sum+=nums[index];
            }
            arr[i]=sum;
        }
        return arr;
    }
}
